Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning

摘要

Many problems in machine learning and other fields can be (re)for-mulated aslinearly constrained separable convex programs. In most of the cases, there aremultiple blocks of variables. However, the traditional alternating directionmethod (ADM) and its linearized version (LADM, obtained by linearizing thequadratic penalty term) are for the two-block case and cannot be naivelygeneralized to solve the multi-block case. So there is great demand onextending the ADM based methods for the multi-block case. In this paper, wepropose LADM with parallel splitting and adaptive penalty (LADMPSAP) to solvemulti-block separable convex programs efficiently. When all the componentobjective functions have bounded subgradients, we obtain convergence resultsthat are stronger than those of ADM and LADM, e.g., allowing the penaltyparameter to be unbounded and proving the sufficient and necessary conditions}for global convergence. We further propose a simple optimality measure andreveal the convergence rate of LADMPSAP in an ergodic sense. For programs withextra convex set constraints, with refined parameter estimation we devise apractical version of LADMPSAP for faster convergence. Finally, we generalizeLADMPSAP to handle programs with more difficult objective functions bylinearizing part of the objective function as well. LADMPSAP is particularlysuitable for sparse representation and low-rank recovery problems because itssubproblems have closed form solutions and the sparsity and low-rankness of theiterates can be preserved during the iteration. It is also highlyparallelizable and hence fits for parallel or distributed computing. Numericalexperiments testify to the advantages of LADMPSAP in speed and numericalaccuracy.